<html>
<head><meta charset="utf-8"><title>Pinned basic blocks? · t-compiler/wg-mir-opt · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/index.html">t-compiler/wg-mir-opt</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html">Pinned basic blocks?</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="194537571"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194537571" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194537571">(Apr 18 2020 at 10:29)</a>:</h4>
<p>This might be very off the rails, but I wanted to write it up at least: what if we gave every basic block (more precisely, <code>BasicBlockData</code>) a stable memory location and effectively made the CFG an intrusive data structure? The <code>BasicBlock(u32)</code> indices might still exist to enable deterministic iteration order and <code>IndexedVec</code> in each pass, but direct and mutual pointers could potentially be helpful elsewhere:</p>
<ul>
<li>When removing blocks, there's no need to walk the whole CFG to update BB numbers and shift <code>BasicBlockData</code>s around in memory (a <code>swap_remove</code> of a newtyped index should suffice).</li>
<li>Consequently, we could maintain predecessor links all the time and get rid of <code>BodyAndCache</code>.</li>
<li>Similarly, other side tables such as dominators could become easier to maintain throughout the pipeline, since they would only have to be informed of the structural CFG changes rather than every renumbering.</li>
<li>If removing dead blocks becomes very cheap, some passes could delete incrementally instead of deferring it to benefit from bulk updates (as long as they don't need a stable block numbering across the deletes).</li>
<li>More speculatively, if <code>BasicBlockData</code> no longer needs to move in memory, perhaps it becomes economical to store the statements inline for short basic blocks (i.e., <code>SmallVec&lt;[Statement; N]&gt;</code>).</li>
<li>While we'd now some unsafe code for CFG manipulations, currently the equivalent (safe but still fiddly) data structure manipulations are open-coded in various passes and encapsulating the unsafe bits would give an opportunity to clean this up.</li>
<li>This is minor and depends on the exact API we end up with, but generally my experience is that direct pointers result in nicer code than always going through newtyped indices.</li>
</ul>



<a name="194539591"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194539591" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194539591">(Apr 18 2020 at 11:26)</a>:</h4>
<p>you don't need actual pointers for this</p>



<a name="194539608"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194539608" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194539608">(Apr 18 2020 at 11:26)</a>:</h4>
<p>I think this is how Cranelift works</p>



<a name="194539758"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194539758" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194539758">(Apr 18 2020 at 11:30)</a>:</h4>
<p><span class="user-mention silent" data-user-id="119009">eddyb</span> <a href="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/Pinned.20basic.20blocks.3F/near/194539608" title="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/Pinned.20basic.20blocks.3F/near/194539608">said</a>:</p>
<blockquote>
<p>I think this is how Cranelift works</p>
</blockquote>
<p>Yes, pretty much. You can append blocks to the <a href="https://docs.rs/cranelift-codegen/0.62.0/cranelift_codegen/ir/layout/struct.Layout.html" title="https://docs.rs/cranelift-codegen/0.62.0/cranelift_codegen/ir/layout/struct.Layout.html">layout</a> in any order.</p>



<a name="194540298"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194540298" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194540298">(Apr 18 2020 at 11:45)</a>:</h4>
<p>Yes, you could also have "stable IDs" instead of stable pointers, but why would you? Most ways to implement such IDs lead to more unnecessary indirection and lookups, and all of them result in inconvenient APIs where you always have to combine the ID with various context objects to do anything. The ability to use integers smaller than a pointer does not seem significant for basic blocks, since they are not as frequently referenced and maintaining such IDs required extra data structures on the side. Until recently, the killer argument was the inability to safely encapsulate intrusive object graphs, but that's exactly what pinning enables nowadays.</p>



<a name="194540561"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194540561" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194540561">(Apr 18 2020 at 11:53)</a>:</h4>
<p>However, I am worried whether mutation of blocks and their contents can be adequately modeled with lifetimes, <code>Pin&lt;&amp;T&gt;</code> vs <code>Pin&lt;&amp;mut T&gt;</code>, and traversal methods. If some kind of interior mutability with runtime checks is needed for the access patterns needed in rustc, in contrast to the "no aliasing guarantees about the indices floating around, but actual mutation goes through short-lived <code>&amp;mut</code>s" style of newtyped indices that would suck.</p>



<a name="194540622"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194540622" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194540622">(Apr 18 2020 at 11:54)</a>:</h4>
<p>This is more of an API design problem independent of how you actually implement it under the hood, but it might eat up some of the advantages of stable pointers (either performance or API simplicity).</p>



<a name="194541528"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194541528" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194541528">(Apr 18 2020 at 12:15)</a>:</h4>
<blockquote>
<p>Most ways to implement such IDs lead to more unnecessary indirection and lookups, and all of them result in inconvenient APIs where you always have to combine the ID with various context objects to do anything. </p>
</blockquote>
<p>IME it works great :P</p>



<a name="194541569"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194541569" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194541569">(Apr 18 2020 at 12:16)</a>:</h4>
<p>and Cranelift is also a success story AFAIK</p>



<a name="194541572"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194541572" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194541572">(Apr 18 2020 at 12:16)</a>:</h4>
<p>compared to worrying about pointers and all of the restrictions that imposes</p>



<a name="194541579"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194541579" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194541579">(Apr 18 2020 at 12:16)</a>:</h4>
<p>frankly we could get a lot of mileage out of just making the start block a field in the <code>mir::Body</code> instead of a constant</p>



<a name="194542845"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194542845" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194542845">(Apr 18 2020 at 12:47)</a>:</h4>
<p>As I said before, I'm not sure there is anything to my idea, especially w.r.t. "can you make the API nice or does the borrow checker get in the way". But I'm curious, and I think basic blocks in MIR have different trade-offs than  MIR statements and Cranelift's basic blocks (e.g., in Cranelift, every single instruction has a parent reference, while in current MIR and under my proposal, most blocks are only referenced from a single digit number of places in total).</p>



<a name="194542921"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194542921" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194542921">(Apr 18 2020 at 12:49)</a>:</h4>
<blockquote>
<p>in Cranelift, every single instruction has a parent reference</p>
</blockquote>
<p>No, the instruction itself doesn't know where it is in the layout. It is stored in the <code>DataFlowGraph</code>, which doesn't know anything about the location of instructions. The <code>Layout</code> is the things that knows where instructions are located.</p>



<a name="194543193"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194543193" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194543193">(Apr 18 2020 at 12:54)</a>:</h4>
<p>Thinking about it again. The <code>Layout</code> <strong>does</strong> have a map from <code>Inst</code> -&gt; <code>Block</code>.</p>



<a name="194543195"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194543195" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194543195">(Apr 18 2020 at 12:54)</a>:</h4>
<p>Sorry, I was imprecise about where it's stored, but there <em>is</em> one BB reference per instruction, right?</p>



<a name="194543215"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194543215" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194543215">(Apr 18 2020 at 12:55)</a>:</h4>
<p>Yes</p>



<a name="194543286"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194543286" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194543286">(Apr 18 2020 at 12:56)</a>:</h4>
<p>Then the point I was trying to make still stands: Cranelift has many more references to blocks, so representing those as smaller integers is more useful than in rustc.</p>



<a name="194543339"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194543339" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194543339">(Apr 18 2020 at 12:57)</a>:</h4>
<p>I don't want integers because they're small, I want them because they're <em>simple</em></p>



<a name="194543409"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194543409" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194543409">(Apr 18 2020 at 12:59)</a>:</h4>
<p>you can just not renumber BBs if you can specify a non-0 starting basic block</p>



<a name="194543416"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194543416" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194543416">(Apr 18 2020 at 12:59)</a>:</h4>
<p>and it's a tradeoff: anything O(BasicBlocks) may get slowed down by the lack of renumbering</p>



<a name="194543423"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194543423" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194543423">(Apr 18 2020 at 12:59)</a>:</h4>
<p>(or worse, superlinear in the number of basic blocks)</p>



<a name="194543657"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194543657" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194543657">(Apr 18 2020 at 13:04)</a>:</h4>
<p>It's not <em>that</em> simple. Today, the renumbering also happens when removing blocks, to keep a compact <code>Vec&lt;BasicBlockData&gt;</code> and corresponding <code>IndexVec</code>s in various passes. If you don't renumber, then you have to start treating it as something like a pool, maintain a free list, deal with non-consecutive IDs somehow, etc.</p>



<a name="194543772"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194543772" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194543772">(Apr 18 2020 at 13:07)</a>:</h4>
<p>or you can just not</p>



<a name="194543840"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194543840" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194543840">(Apr 18 2020 at 13:09)</a>:</h4>
<p>like I said, it's a tradeoff and you can choose to keep it simple at the cost of some later perf loss (which could be marginal, depending on the input and what you're doing to it)</p>



<a name="194543995"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194543995" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194543995">(Apr 18 2020 at 13:13)</a>:</h4>
<p>There are definitely many trade-offs in this area, but FWIW if not freeing dead basic blocks is an option you're willing to entertain, then most of the implementation complexity relating to pointers goes away too.</p>



<a name="194544011"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194544011" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194544011">(Apr 18 2020 at 13:13)</a>:</h4>
<p>the difference is mutation</p>



<a name="194544018"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194544018" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194544018">(Apr 18 2020 at 13:13)</a>:</h4>
<p>if you can get away with interning then yes. otherwise, pointers are still a nightmare to mutate behind</p>



<a name="194544191"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194544191" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194544191">(Apr 18 2020 at 13:17)</a>:</h4>
<p>We're getting to a point where it's so conceptual that I don't think it makes much sense to continue like this. Maybe I'll noodle around with API design and find something concrete that maybe works and we can talk about its trade-offs, or maybe I won't.</p>



<a name="194544367"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194544367" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194544367">(Apr 18 2020 at 13:22)</a>:</h4>
<p>maybe I should make it really clear that I've gone off the deep end on interning entire DAG IRs using integers, and ended up loving it, and neither interning nor integers might be a good fit for MIR</p>



<a name="194544435"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194544435" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194544435">(Apr 18 2020 at 13:23)</a>:</h4>
<p>but combining pointers with mutation for a graph also gives me a really unsettling vibe. like a kneejerk I suppose</p>



<a name="194544454"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194544454" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194544454">(Apr 18 2020 at 13:23)</a>:</h4>
<p>oh yeah it's sharing + mutation. duh</p>



<a name="194544513"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194544513" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194544513">(Apr 18 2020 at 13:24)</a>:</h4>
<p>if you use interior mutability inside each block then it's probably fine</p>



<a name="194544594"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194544594" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194544594">(Apr 18 2020 at 13:26)</a>:</h4>
<p>I guess "intrusive linked list" could mean you start with a <code>&amp;mut</code> for the entry/start block and can mutate anywhere in the  CFG by following the edges? that seems pretty restricted tbh</p>



<a name="194544605"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194544605" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194544605">(Apr 18 2020 at 13:26)</a>:</h4>
<p>there are some things that use <code>Location</code> to index a statement/terminator in O(1)</p>



<a name="194544608"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194544608" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194544608">(Apr 18 2020 at 13:26)</a>:</h4>
<p>and mutate it</p>



<a name="194544616"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194544616" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194544616">(Apr 18 2020 at 13:27)</a>:</h4>
<p>that seems hard w/ pointers and w/o interior mutability</p>



<a name="194544856"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194544856" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194544856">(Apr 18 2020 at 13:32)</a>:</h4>
<p>This kind of "could touch anything" mutation seems to require (short-lived) mutable access to the whole <code>Body</code> anyway, no matter whether you use pointers or IDs, so the only question is whether you need to do it while holding references to other things derived from the <code>Body</code>. I think for basic blocks this is more feasible to avoid than for statements, but we'll see.</p>



<a name="194585841"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194585841" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194585841">(Apr 19 2020 at 08:23)</a>:</h4>
<p><span class="user-mention silent" data-user-id="119009">eddyb</span> <a href="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/Pinned.20basic.20blocks.3F/near/194543339" title="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/Pinned.20basic.20blocks.3F/near/194543339">said</a>:</p>
<blockquote>
<p>I don't want integers because they're small, I want them because they're <em>simple</em></p>
</blockquote>
<p>pointers were simple. then we (as in compiler engineers) made them complicated. now we need to resort to integers and reinvent that wheel. ;)</p>



<a name="194587888"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194587888" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194587888">(Apr 19 2020 at 09:20)</a>:</h4>
<p>For the record: I took a stab at this idea and quickly became very frustrated with how badly interior mutability composes with the collections needed for the successor/predecessor links. For a bunch of things, a <code>Cell&lt;Vec&lt;_&gt;&gt;</code> works (badly) if you <code>take()</code> it temporarily and restore it after the (non-reentrant) modification, but I quit by the time I got to successor/predecessor iterators. I can see a way to make them work (store pointer to block and an index) but given the lack of aliasing guarantees, I expect this would  generally optimize badly (extra loads and bounds check on every iteration).</p>
<p>And then there's the old issue of iterator invalidation: I can make it safe to modify the CFG structure while iterating, but it likely indicates a bug whenever it happens, and it would be better to rule this out statically. Which is precisely what mutable-xor-shared enables and interior mutability doesn't. I've been thinking about ways to uphold "need &amp;mut to modify the CFG structure" but when each block contains some interior-mutable pieces, it's hard to square "can hold exclusive access to multiple blocks" with "mutating one block fiddles with some data in another block", and even if you only needed mutable access to one block at a time, special care would be needed around self-loops.</p>



<a name="194588941"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194588941" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194588941">(Apr 19 2020 at 09:48)</a>:</h4>
<p>From this perspective, I would say the advantage of integers isn't simplicity, it's that they are more dumb and kind of circumvent the borrow checker. By not tracking that they're effectively a shared reference to some data in the CFG outside of when you actually access that data, they enable you to create temporary mutable borrows when you need them because there's no conflicting long-lived shared borrows. Which makes them a little like <code>&amp;RefCell&lt;BasicBlockData&gt;</code>! Except that  dynamic checks are replaced with more coarse-grained static borrows of the whole <code>Body</code>: instead of <code>bb.borrow_mut()</code> preventing concurrent access to the same block, you do <code>&amp;mut body.statements[bb]</code> and statically rule out access to <em>any</em> other basic block.</p>



<a name="194592101"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Pinned%20basic%20blocks%3F/near/194592101" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Hanna Kruppe <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Pinned.20basic.20blocks.3F.html#194592101">(Apr 19 2020 at 11:11)</a>:</h4>
<p>I believe the same API pattern (untracked handles that can be upgraded to real references via a borrow of the <code>Body</code>) can be ported to direct pointers too, but some extra cleverness  is needed to limit the blast radius of dangling handles (integer IDs easily avoid UB by bounds checking against the underlying <code>Vec</code>) and while there are some ways to use lifetimes for this without conflicting with the mutable borrows needed for the actual data accesses, as far as I can tell this makes the API way too convoluted to be worth it.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>